package com.lisp.algorithm.leetcode;

import com.lisp.algorithm.util.ArrayUtil;

public class Inversion {

	public static void main(String[] args) {
		char[] chars = "(ed(et(oc))el)".toCharArray();
		ArrayUtil.print(inversion(chars));
	}
	
	private static char[] inversion(char[] data) {
		Stack s = new Stack();
		Queue q = new Queue();
		for(int i=0, len=data.length; i<len; i++) {
			char c = data[i];
			if(c == ')') {
				char mainPoped = s.pop();
				while(mainPoped != '(') {
					q.enqueue(mainPoped);
					mainPoped = s.pop();
				}
				
				while(!q.isEmpty()) {
					s.push(q.dequeue());
				}
			} else {
				s.push(c);
			}
		}
		
		return s.getData();
	}
	
	static class Stack {
		char data[] = new char[2000];
		int top = -1;
		
		private void push(char c) {
			top++;
			data[top] = c;
		}
		
		private char pop() {
			char ret = data[top];
			top--;
			return ret;
		}
		
		private char[] getData() {
			char[] ret = new char[2000];
			System.arraycopy(data, 0, ret, 0, top+1);
			return ret;
		}
	}
	
	static class Queue {
		char data[] = new char[2000];
		int head = 0;
		int tail = 0;
		
		private void enqueue(char c) {
			data[tail] = c;
			tail++;
		}
		
		private char dequeue() {
			char ret = data[head];
			head++;
			return ret;
		}
		
		private boolean isEmpty() {
			return head == tail;
		}
	}
}
